% \begin{itemize}
% \item given assignment, compute the maximum delay.
% \item the iterative equation + proofs
% \item Explain how an exhaustive enumeration of all request-to-bus-slot assignment can solve the problem
% \end{itemize}
In this section, we first describe a method to compute the maximum waiting time given a single request, a free bus slot and the bus availability model. The same rationale is then extended to compute the cumulative
waiting time for the sequence of request of a given task in conformance to certain constraints. For a given request-to-slot assignment (i.e  when request k of task $\tau_i$ is assigned in slot $\Assignment{i}{k}$) the key idea is to release the request as early as possible and delay the servicing of the request to the latest possible time of the given slot.
In other words, for the given slot we need to determine the \emph{lower} bound on the release time of a request, an \emph{upper} bound on the service time of a request for the given slot and
then compute the resulting waiting time. A set of lemmas are provided below as foundations to this central theme. 

\begin{Property}
By construction, $\Tmax{i}{1}$ is the longest waiting time for one request before which it can be assigned a free bus slot.
This is because the underlying algorithm to compute this value (see~\cite{Icess12} for details) considers the ordering of tasks in a core in a manner in which they issue the maximum memory requests in a given time interval.
\end{Property}

% 
% \begin{figure}[!ht]
% \centering
% \includegraphics*[width=1\linewidth, viewport = 0 0 720 450]{../figures/lemma1.pdf}
% \caption{Visualization of the reasoning used in the proof of Lemma~\ref{lem:releaseLB}}.
% \label{fig:lemma1}
% \end{figure}
\subsection{Maximum delay for a single request-to-slot assignment}
\label{sec:maxdelay_single}
\begin{lemma}[Lower bound on the release time of a request]
\label{lem:releaseLB}
For any task $\tau_i \in \tau$ and for all $k > 1$, let $\request{i}{k-1}$ and $\request{i}{k}$ be two consecutive requests generated by $\tau_i$. For a given request-to-slot assignment $\Assignment{i}{k-1}$ and $\Assignment{i}{k}$, if request $\request{i}{k-1}$ has been served at time $\reqserv{i}{k-1}$ in the $\Assignment{i}{k-1}$'th free bus slot then it holds that
\begin{equation}
\label{equ:LBreqrel}
\reqrel{i}{k} \geq \max(\Tmin{i}{\Assignment{i}{k} - 1} + 1, \reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1})
\end{equation}
\end{lemma}
\begin{proof}
First, given that $\request{i}{k}$ is served when the bus is free for the $\Assignment{i}{k}$'th time, it immediately follows that $\request{i}{k}$ must have been released \emph{after} the bus was free for the $(\Assignment{i}{k} - 1)$'th time; Otherwise $\request{i}{k}$ would have been served in that $(\Assignment{i}{k} - 1)$'th free slot instead of the $\Assignment{i}{k}$'th. Since the \emph{earliest} time-instant at which the bus can be free for the $(\Assignment{i}{k} - 1)$'th time is $\Tmin{i}{\Assignment{i}{k} - 1}$ and since $\request{i}{k}$ must have been released afterwards, the earliest time-instant at which it can have been released is $\Tmin{i}{\Assignment{i}{k} - 1} + 1$, which gives the left-hand side of the max operator of Inequality~\eqref{equ:LBreqrel}. 
%Figure~\ref{fig:lemma1} gives a visualization of the demonstration.

Second, given that request $\request{i}{k-1}$ has been served in the $\Assignment{i}{k-1}$'th free slot at time $\reqserv{i}{k-1}$, the \emph{earliest} time-instant at which the bus can be available to $\tau_i$ for the $\Assignment{i}{k}$'th time is given by $\reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1}$; This lower-bound is obtained by assuming that all the bus slots are available to $\tau_i$ from time $\reqserv{i}{k-1}$ onward. Under this scenario, if request $\request{i}{k}$ was released before time-instant $\reqserv{i}{k-1} + \Assignment{i}{k} - \Assignment{i}{k-1}$ then instead of being served in the $\Assignment{i}{k}$'th free bus slot as assumed, $\request{i}{k}$ would have been served earlier, in one of those free bus slots between the $\Assignment{i}{k-1}$'th and the $\Assignment{i}{k}$'th. This gives the right-hand term of Inequality~\eqref{equ:LBreqrel}.
\end{proof}
\begin{lemma}[Upper bound on the service time of a request]
\label{lem:UBreqserv}
For any task $\tau_i \in \tau$ and for all $k > 1$, if request $\request{i}{k}$ is served at time $\reqserv{i}{k}$ in the $\Assignment{i}{k}$'th free bus slot then it holds that
\begin{equation}
\label{equ:UBreqserv}
\reqserv{i}{k} \leq \min(\Tmax{i}{\Assignment{i}{k}}, \reqrel{i}{k} + \Tmax{i}{1})
\end{equation}
\end{lemma}
\begin{proof}
Given that $\request{i}{k}$ is served in the $\Assignment{i}{k}$'th free bus slot, it follows from the definition of the function $\Tmax{i}{}$ that $\request{i}{k}$ cannot be served later than the latest possible time-instant at which that slot can be available, i.e. it is served no later than $\Tmax{i}{\Assignment{i}{k}}$ (left-hand term of the min operator). It follows by construction that a request $\request{i}{k}$ cannot be served more than $\Tmax{i}{1}$ units after its release, which gives the right-hand term of the min operator of Inequality~\eqref{equ:UBreqserv}.
\end{proof}
The maximum delay for servicing the given request $k$ in slot $\Assignment{i}{k}$  is then given by $\reqserv{i}{k} - \reqrel{i}{k}$.
\subsection{Maximum cumulative delay for a request-to-slot mapping}
In the previous section we established a method to compute an upper bound on the delay for a given request-to slot pair. 
Next, for a given task $\tau_i$ with $\NbReqPerTask{i}$ requests and a choice of feasible slots, there are say, $\gamma$ possible
sets of distinct $\NbReqPerTask{i}$ request-to-slot assignments.

To maximize the cumulative delay, for each of these sets of assignments, we can first compute the individual delays incurred for each request-to-slot pair by applying the lemmas described above (in Section~\ref{sec:maxdelay_single}). Next we can compute the cumulative delay for that set (by summation) and finally select the set such that the cumulative delay is maximized.
However, since the assignment of a given request is dependent on the assignment of the previous one, we can only compute the maximized delay as a summation of individual delays,
if the Lemmas in Section~\ref{sec:maxdelay_single} hold true for a \emph{sequence of requests}. The subsequent lemmas establish the same. 

% For any task $\tau_i$, given a request-to-free-bus-slot assignment $\Assignment{i}{k}$ for each of the $\NbReqPerTask{i}$ requests $\request{i}{k}$ that $\tau_i$ can generate, the cumulative waiting time $\DelayOne{i}{x} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
\begin{lemma}[Worst-case cumulative delay]
\label{lem:wccd} 
Let $A = \{ \AssignmentOne{i}{1}, \ldots, \AssignmentOne{i}{\NbReqPerTask{i}} \}$ refer to a request-to-slot mapping for the $\NbReqPerTask{i}$ requests of task $\tau_i$. Let $\DelayOne{i}{\NbReqPerTask{i}}$ be the maximum cumulative delay for these $\NbReqPerTask{i}$ requests considering this mapping $A$. Then $\DelayOne{i}{\NbReqPerTask{i}} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
% For any task $\tau_i$, given a request-to-free-bus-slot assignment $\Assignment{i}{k}$ for each of the $\NbReqPerTask{i}$ requests $\request{i}{k}$ that $\tau_i$ can generate, the cumulative waiting time $\DelayOne{i}{}, \NbReqPerTask{i}} = \sum_{k=1}^{\NbReqPerTask{i}} \reqserv{i}{k} - \reqrel{i}{k}$ of all these requests is maximized for:
\begin{eqnarray}
\label{equ:reqrel1} \reqrel{i}{1} & = & \Tmin{i}{\Assignment{i}{1} - 1} + 1 \\
\label{equ:reqserv1} \reqserv{i}{1} & = & \min(\Tmax{i}{\Assignment{i}{1}}, \reqrel{i}{1} + \Tmax{i}{1})
\end{eqnarray}
and $\forall k \in [2, \NbReqPerTask{i}]$,
\begin{footnotesize}
\begin{eqnarray}
\label{equ:reqrelk} \reqrel{i}{k} & = & \max( \Tmin{i}{\Assignment{i}{k} - 1} + 1, \reqserv{i}{k-1} + (\Assignment{i}{k} - \Assignment{i}{k-1}) ) \\
\label{equ:reqservk} \reqserv{i}{k} & = & \min( \Tmax{i}{\Assignment{i}{k}}, \reqrel{i}{k} + \Tmax{i}{1} )
\end{eqnarray}
\end{footnotesize}
\end{lemma}
With Lemma~\ref{lem:wccd}, we established that the summation of the individual maximum request-to-slot assignments leads to the cumulative delays for a particular set of assignment.
Next we will formulate a method to \emph{select} such a set amongst the $\gamma$ candidate sets.
While an obvious brute-force is available, it is computationally expensive and hence the next section proposes a better method for the same.
Please refer to proof in the appendix. 
